package medium打家劫舍III;

public class Solution {

    //超出时间限制
    public int rob1(TreeNode root) {
        return test(root, 0);
    }

    public int test(TreeNode root , int signal){
        if (root == null)
            return 0;
        int a = 0;
        int b = 0;
        if (signal == 0){
            a = root.val + test(root.left, 1) + test(root.right, 1);
        }
        b = test(root.left, 0) + test(root.right, 0);
        return Math.max(a,b);
    }

    public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }

    public int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int selected = node.val + l[1] + r[1];
        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{selected, notSelected};
    }

}
